import java.util.LinkedList;
import java.util.Queue;

public class Test {
    //
    public static void main(String[] args) {
        //
    }
}
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public int numEnclaves(int[][] grid) {

        int m = grid.length, n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        // 1. 把边上的 1 全部加⼊到队列中
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(i == 0 || i == m - 1 || j == 0 || j == n - 1)
                {
                    if(grid[i][j] == 1)
                    {
                        q.add(new int[]{i, j});
                        vis[i][j] = true;
                    }
                }
        // 2. 多源 bfs
        while(!q.isEmpty())
        {
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for(int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 &&
                        !vis[x][y])
                {
                    q.add(new int[]{x, y});
                    vis[x][y] = true;
                }
            }
        }
        // 3. 提取结果
        int ret = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(grid[i][j] == 1 && !vis[i][j])
                    ret++;
        return ret;
    }
}
